#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
from array import array
from time import time

DEBUG = 0 # 1 para exibir pares, 2 para saida mais detalhada

SUCESSO = 0
FALHA = -1
DESISTENCIA = 999

TAM_DIC = 255

def deslocar(buffer, delta):
    """desloca o buffer delta posicoes em direcao `a posicao 0"""
    for i in xrange(delta,len(buffer)):
        buffer[i-delta]=buffer[i]    
    
def codifica(buffer,pos_ini, pos_ult):
    """determina o par (dist, compr) para o próximo trecho a ser comprimido"""
    pos = pos_ini
    max_car_iguais = 0
    pos_max = 0
    while pos < TAM_DIC:
        car_iguais = 0
        while ((car_iguais < TAM_DIC) and ((TAM_DIC+car_iguais)<=pos_ult)
            and (buffer[pos+car_iguais] == buffer[TAM_DIC+car_iguais])):
            car_iguais += 1
        # if (car_iguais > 1) and (car_iguais > max_car_iguais):
        if car_iguais >= max_car_iguais:
            max_car_iguais = car_iguais
            pos_max = pos
        pos += 1
    if max_car_iguais:
        dist = TAM_DIC-pos_max
        compr = max_car_iguais
        cars = ''.join([chr(b) for b in buffer[TAM_DIC:TAM_DIC+compr]])
    else:
        dist = 0
        compr = buffer[TAM_DIC]
        cars = chr(compr)
    if DEBUG == 1:
        print "%3d %3d %s" % (dist, compr, repr(cars))
    return (dist, compr)

def comprimir(entrada, saida, buffer):
    """le o arquivo de entrada, comprime e grava o de saida, usando o buffer"""
    pos_ini = TAM_DIC       # pos do primeiro caractere no dicionario
    tam_ent = 0
    tam_sai = 0
    for i in range(TAM_DIC):
        c = entrada.read(1)
        if not c: 
            break
        buffer[TAM_DIC+i] = ord(c)
        tam_ent += 1

    pos_ult = TAM_DIC + tam_ent - 1 # pos do ultimo caractere no look-ahead   

    if DEBUG == 2:
        print '_'*TAM_DIC
        print buffer.tostring()
    while pos_ult >= TAM_DIC: 
        dist, compr = codifica(buffer,pos_ini, pos_ult)
        if DEBUG == 2: msg = "%2d %s" % (dist, compr)
        saida.write(chr(dist)+chr(compr))
        if dist == 0:
            compr = 1 # deslocar tb. quando o caractere não foi achado
        tam_sai += 2
        deslocar(buffer, compr)
        pos_ini -= compr
        if pos_ini < 0: pos_ini = 0
        for i in xrange(compr,0,-1):
            c = entrada.read(1)
            if c:
                buffer[-i] = ord(c)
                tam_ent += 1
            else:
                pos_ult -= 1
        if DEBUG == 2:
            print '_'*TAM_DIC + ' '*TAM_DIC + msg
            print buffer.tostring()
    #print "%7d bytes lidos, %7d bytes gravados" % (tam_ent, tam_sai),
    razao = (float(tam_ent-tam_sai)/tam_ent) * 100.0
    if not DEBUG:
        if tam_sai > tam_ent:
            print >>sys.stderr, "AVISO: o arquivo gerado ficou %.2f%% maior que o original." % (-razao)
            print "\t*EXPANSAO*: %6.2f%%" % (-razao),
        else:
            print "\tcompressao: %6.2f%%" % (razao),
    return SUCESSO
        
def descomprimir(entrada, saida, buffer):        
    """le o arquivo de entrada, descomprime e grava o de saida, usando o buffer"""
    pos_ini = TAM_DIC       # pos do primeiro caractere no dicionario
    pos_ult = TAM_DIC*2 - 1 # pos do ultimo caractere no look-ahead
    
    tam_ent = 0
    tam_sai = 0
    
    par = entrada.read(2)
    while len(par) == 2:
        if DEBUG == 2:
            print '_'*TAM_DIC
            print buffer.tostring()
        tam_ent += 2
        dist = ord(par[0])
        if dist == 0:
            compr = 1
            byte = ord(par[1])
            saida.write(chr(byte))
            buffer[TAM_DIC] = byte
        else:
            compr = ord(par[1])
            for pos in range(compr):
                byte = buffer[TAM_DIC-dist+pos]
                buffer[TAM_DIC+pos] = byte
                saida.write(chr(byte))
            #saida.write(buffer[TAM_DIC:TAM_DIC+compr])
        deslocar(buffer, compr)
        tam_sai += compr
        par = entrada.read(2)
    
    # print "%7d bytes lidos, %7d bytes gravados" % (tam_ent, tam_sai),
    if len(par) == 1:
        print >>sys.stderr, "ERRO: arquivo de entrada invalido (comprimento impar)"
        return FALHA
    else:
        return SUCESSO
    
def main():
    buffer = array('B',[0]*(TAM_DIC*2))
    resultado = 0
    
    if len(sys.argv) > 1:
        for nome_arq in sys.argv[1:]:
            entrada = file(nome_arq,'rb')
            t0 = time()
            if nome_arq.endswith('.lz'):
                nome_arq_sai = nome_arq[:-3] + '.desc'
                saida = file(nome_arq_sai,'wb')
                print "descomprimindo %-25s" % nome_arq_sai,
                resultado += descomprimir(entrada, saida, buffer)        
            else:
                nome_arq_sai = nome_arq+'.lz'
                saida = file(nome_arq_sai,'wb')
                if not DEBUG:
                    print "comprimindo %-25s" % nome_arq_sai,
                resultado += comprimir(entrada, saida, buffer)
            if not DEBUG:
                print '\ttempo: %7.2fs' % (time() - t0)
            entrada.close()
            saida.close()
    else:
        op = 0
        while op != 1 and op != 2:
            print "[1] compressao; [2] descompressao - escolha a operacao: ",
            op = raw_input()
            if len(op) == 0:
                sys.exit(DESISTENCIA)
            else:
                try:
                    op = int(op)
                except ValueError:
                    continue
        entrada = None
        while entrada is None:
            print "nome do arquivo de entrada:",
            nome_arq = raw_input()
            try:
                if len(nome_arq) == 0:
                    sys.exit(DESISTENCIA)
                entrada = file(nome_arq,'rb')
            except IOError, e:
                print e.strerror
        saida = None
        while saida is None:
            print "nome do arquivo de saida:  ",
            nome_arq = raw_input()
            try:
                if len(nome_arq) == 0:
                    sys.exit(DESISTENCIA)
                saida = file(nome_arq,'wb')
            except IOError, e:
                print e.strerror
        if op == 1:
            resultado += comprimir(entrada, saida, buffer)
        else:
            resultado += descomprimir(entrada, saida, buffer)
    
    return resultado

if __name__ == '__main__':
    main()
